<!--This file created 8:38 AM  7/2/97 by Claris Home Page version 2.0-->
<HTML>
<HEAD>
   <TITLE>GEF Design Presentation</TITLE>
   <META NAME=GENERATOR CONTENT="Claris Home Page 2.0">
   <X-SAS-WINDOW TOP=0 BOTTOM=619 LEFT=0 RIGHT=611>
</HEAD>
<BODY BGCOLOR="#FFFFFF">

<H2> This file has not been updated for GEF v0.6 yet. </H2>

<H1><CENTER>The Design of GEF (the Graph Editing Framework)
</CENTER></H1>

<H2><CENTER>Presented by Jason Robbins<BR>

<A HREF="mailto:jrobbins&#064;tigris.org">jrobbins&#064;tigris.org</A>
</CENTER></H2>

<H2>Overview:</H2>

<UL>
   <LI><A HREF="#What">What is GEF?</A>
   
   <LI><A HREF="#Why">Why design a graph editing framework?</A>
   
   <LI><A HREF="#Requirements">Requirements</A>
   
   <LI><A HREF="#Design Overview">Design overview</A>, OMT diagram
   
   <LI>CRC Cards
   
   <LI>Use cases (with audience participation)
   
   <UL>
      <LI><A HREF="#Adding a node">Adding a node to the diagram</A>
      
      <LI><A HREF="#Selecting multiple">Selecting multiple
      objects</A>
      
      <LI><A HREF="#Drawing a polygon">Drawing a polygon</A>
      
      <LI><A HREF="#Booch">Implementing a Booch class browser</A>
   </UL>
   
   <LI><A HREF="#Open design problems">Open design problems and
   issues</A>
   
   <LI><A HREF="#previous work">Some previous work on graph
   editing</A>
</UL>

<H2><A NAME="What"></A>
<HR>
What is GEF?</H2>

<P>GEF is a java class library that supports the construction of
graph editing applications, i.e., applications that include the
ability to draw structured and unstructured diagrams. GEF itself is
not a drawing program, it supports the construction of custom drawing
programs for particular domains.</P>

<P><IMG SRC="screenshots/net2.gif" WIDTH=256 HEIGHT=178
X-SAS-UseImageWidth X-SAS-UseImageHeight ALIGN=bottom><IMG
SRC="screenshots/selections.gif" WIDTH=256 HEIGHT=178
X-SAS-UseImageWidth X-SAS-UseImageHeight ALIGN=bottom></P>

<H2><A NAME="Why"></A>
<HR>
Why design a graph editing framework?</H2>

<P>Many research projects need simple visualizations of models that
can be viewed as connected graphs. Having a good graph editing
framework would save a lot of people a lot of work and would make
better research products. The hard part is making a framework that
provides substancial value to a wide range of people.</P>

<P>Also, designing a graph editor is a very satisfying task. The
design can be very concrete in its object-oriention, dimentions of
extensibility are easy to imagine, the resulting tool is fun to use.
Coming up with a good design that is powerful and adoptable is very
chalenging, but satisfying.</P>

<P>Several people have already implemented graph drawing tools. I
needed one that was written in Java and could be freely distributed.
</P>

<H2><A NAME="Requirements"></A>
<HR>
Requirements</H2>

<P>When I started the project I set these goals:</P>

<P><TABLE BORDER=0>
   <TR>
      <TD WIDTH=241>
         <P><B>What</B>
      </TD><TD>
         <P><B>Why</B>
      </TD></TR>
   <TR>
      <TD WIDTH=241>
         <P>Edit connected graphs
      </TD><TD>
         <P>SE concepts modeled well by graphs
      </TD></TR>
   <TR>
      <TD WIDTH=241>
         <P>Nodes, Ports, Arcs
      </TD><TD>
         <P>More powerful than simple Nodes and Arcs
      </TD></TR>
   <TR>
      <TD WIDTH=241>
         <P>Multiple views on graphs
      </TD><TD>
         <P>Allows separation of concerns
      </TD></TR>
   <TR>
      <TD WIDTH=241>
         <P>Standard look-and-feel as much as possible
      </TD><TD>
         <P>Allows self-guided demos over the web
      </TD></TR>
   <TR>
      <TD WIDTH=241>
         <P>Drawing capabilities like MacDraw
      </TD><TD>
         <P>Unstructured annotations improve most tools
      </TD></TR>
   <TR>
      <TD WIDTH=241>
         <P>Potential users can understand and use GEF in less than
         10 weeks
      </TD><TD>
         <P>Lowers adoption barriers and allows undergraduates to
         contribute
      </TD></TR>
   <TR>
      <TD WIDTH=241>
         <P>New features can be added without modifying the framework
         itself
      </TD><TD>
         <P>General library design guideline. Simplifies releases and
         integration of contributed code
      </TD></TR>
   <TR>
      <TD WIDTH=241>
         <P>Runs in java
      </TD><TD>
         <P>Good language. Gives better demos.
      </TD></TR>
   <TR>
      <TD WIDTH=241>
         <P>Good performace even on slow machines
      </TD><TD>
         <P>Important for web demos
      </TD></TR>
</TABLE>For a current list of GEF features, click
<A HREF="features.html">here</A>.</P>

<H2><A NAME="Design Overview"></A>
<HR>
Design Overview</H2>

<P>There are nine major concepts/classes (and about 90 minor ones):
</P>

<P><TABLE BORDER=0 WIDTH="100%">
   <TR>
      <TD>
         <P><B><TT><A HREF="#Editor">Editor</A></TT></B>
      </TD><TD>
         <P><B><TT><A HREF="#Mode">Mode</A></TT></B>
      </TD><TD>
         <P><B><TT><A HREF="#Layer">Layer</A></TT></B>
      </TD></TR>
   <TR>
      <TD>
         <P><B><TT><A HREF="#DiagramElement">DiagramElement</A></TT></B>
      
      </TD><TD>
         <P><B><TT><A HREF="#NetPrimitive">NetPrimitive</A></TT></B>
      </TD><TD>
         <P><B><TT><A HREF="#Action">Action</A></TT></B>
      </TD></TR>
   <TR>
      <TD>
         <P><B><TT><A HREF="#Selection">Selection</A></TT></B>
      </TD><TD>
         <P><B><TT><A HREF="#RedrawManager">RedrawManager</A></TT></B>
      
      </TD><TD>
         <P><B><TT>Palette</TT></B>
      </TD></TR>
</TABLE>The requirement that new features can be added without
modifying existing code had the largest impact on the design. The
most obvious design would have involved a heavy-weight
<TT>Editor</TT> object that provides lots of functionality, and could
be extended via subclassing. I rejected that because it made the code
less understandable, and because people need to be able to pick and
choose features, not just add more.</P>

<UL>
   <LI><TT>Editor</TT>s are "root objects" that hold together the
   objects that really do the work. An <TT>Editor</TT> does no work
   itself, it just coordinates the other objects. Desipte this
   design, <TT>Editor</TT> is still the largest and most complex
   class.
   
   <LI><TT>Mode</TT>s interpert user input and instantiate
   <TT>Action</TT>s.
   
   <LI><TT>Layer</TT>s contain the objects to be drawn.
   
   <LI><TT>DiagramElement</TT>s are the objects to be drawn.
   
   <LI><TT>NetPrimitive</TT> is the parent class of all Nodes, Ports,
   and Arcs.
   
   <LI><TT>Action</TT>s modify the state of the model, record
   individual modifications.
   
   <LI><TT>Selection</TT>s indicate the target of the next
   <TT>Action</TT>.
   
   <LI><TT>RedrawManager</TT> does efficent screen updates.
   
   <LI><TT>Palette</TT> contains buttons for common functions (no CRC
   card).
   
   <LI><TT>Guide</TT> constrains user mouse coordinates to help make
   an organized looking diagram. (no CRC caard).
</UL>

<P>For a OMT diagram showing many of the classes of GEF, click here.
</P>

<P><A NAME="Editor"></A>
<HR>
<TABLE BORDER=1>
   <TR>
      <TD>
         <H2>Editor</H2>
      </TD><TD ROWSPAN=3>
         <P><IMG SRC="screenshots/editor.gif" WIDTH=256 HEIGHT=178
         X-SAS-UseImageWidth X-SAS-UseImageHeight ALIGN=bottom></P>
         
         <P>An <TT>Editor</TT> in its own window frame showing a
         <TT>LayerGrid</TT> and no <TT>DiagramElement</TT>s. The menu
         is part of the editor. <TT>Editor</TT>s can also exist in
         the web browser's window frame.
      </TD></TR>
   <TR>
      <TD ROWSPAN=2>
         <H3>Responsibilities</H3>
         
         <UL>
            <LI>Serve as a root object for applications
            
            <LI>Coordinate the activity of other objects
            
            <LI>Pass events to <TT>Mode</TT>s for interpretation
            
            <LI>Keep track of <TT>Selections</TT>
            
            <LI>Execute <TT>Action</TT>s in a safe context
            
            <LI>Provide menus, if appropriate
            
            <LI>Store current default line color, fill color, etc.
            
            <LI>Record Undo History (future)
         </UL>
         
         <H3>Collaborators</H3>
         
         <UL>
            <LI><TT>Mode</TT>
            
            <LI><TT>Selection</TT>
            
            <LI><TT>Layer</TT>
            
            <LI><TT>RedrawManager</TT>
            
            <LI><TT>Action</TT>
         </UL>
      </TD></TR>
   <TR></TR>
</TABLE></P>

<P><A NAME="Mode"></A>
<HR>
<TABLE BORDER=1>
   <TR>
      <TD>
         <H2>Mode</H2>
      </TD><TD ROWSPAN=3>
         <P><IMG SRC="screenshots/modeSelect.gif" WIDTH=256
         HEIGHT=178 X-SAS-UseImageWidth X-SAS-UseImageHeight
         ALIGN=bottom></P>
         
         <P><TT>ModeSelect</TT> at work. The user has dragged the
         mouse, starting from blank space in the lower left to the
         upper right. The selection rectangle is drawn by
         <TT>ModeSelect</TT>.
      </TD></TR>
   <TR>
      <TD ROWSPAN=2>
         <H3>Responsibilities</H3>
         
         <UL>
            <LI>Interpert user input
            
            <LI>Instantiate <TT>Action</TT>s for execution in the
            <TT>Editor</TT>
            
            <LI>Determine the next <TT>Mode</TT>, if needed
            
            <LI>Draw (transient) graphics to indicate state
            
            <LI><TT>ModeModify</TT> takes care of moving and resizing
            
            <LI>Subclasses of <TT>ModeCreate</TT> create
            <TT>DiagramElements</TT>
         </UL>
         
         <H3>Collaborators</H3>
         
         <UL>
            <LI><TT>Editor</TT>
            
            <LI><TT>Action</TT>
         </UL>
      </TD></TR>
   <TR></TR>
</TABLE></P>

<P><A NAME="Layer"></A>
<HR>
<TABLE BORDER=1>
   <TR>
      <TD WIDTH=287>
         <H2>Layer</H2>
      </TD><TD ROWSPAN=3>
         <P><IMG SRC="screenshots/selections.gif" WIDTH=256
         HEIGHT=178 X-SAS-UseImageWidth X-SAS-UseImageHeight
         ALIGN=bottom></P>
         
         <P>Here are three layers: <TT>LayerGrid</TT> computes and
         draws the backgronud grid, <TT>LayerDiagram</TT> stores and
         draws some <TT>DiagramElement</TT>s, <TT>LayerComposite</TT>
         contains these two <TT>Layer</TT>s and maintains
         back-to-front ordering of sublayers.
      </TD></TR>
   <TR>
      <TD ROWSPAN=2 WIDTH=287>
         <H3>Responsibilities</H3>
         
         <UL>
            <LI>Draw objects
            
            <LI>Notify dependant <TT>Layer</TT>s or <TT>Editor</TT>s
            of changes
            
            <LI>Pass events to <TT>DiagramElement</TT>s
            
            <LI>Maintain back-to-front ordering of
            <TT>DiagramElement</TT>s
         </UL>
         
         <H3>Collaborators</H3>
         
         <UL>
            <LI><TT>Editor</TT>
            
            <LI><TT>DiagramElement</TT>
         </UL>
      </TD></TR>
   <TR></TR>
</TABLE></P>

<P><A NAME="DiagramElement"></A>
<HR>
<TABLE BORDER=1>
   <TR>
      <TD WIDTH=285>
         <H2>DiagramElement</H2>
      </TD><TD ROWSPAN=3>
         <P><IMG SRC="screenshots/setattr2.gif" WIDTH=335 HEIGHT=296
         X-SAS-UseImageWidth X-SAS-UseImageHeight ALIGN=bottom></P>
         
         <P>Here are a <TT>FigCircle</TT> and a <TT>FigPoly</TT>,
         both are subclassed from <TT>DiagramElement</TT>.
      </TD></TR>
   <TR>
      <TD ROWSPAN=2 WIDTH=285>
         <H3>Responsibilities</H3>
         
         <UL>
            <LI>Draw itself
            
            <LI>Notify dependents of state changes
            
            <LI>Handle some events, e.g., removing a vertex from a
            polygon
            
            <LI>Specify its perfered type of <TT>Selection</TT>
            
            <LI>Keep track of its own line color, fill color, ...
            
            <LI><TT>Perspective</TT>s are <TT>DiagramElement</TT>s
            that present a <TT>NetNode</TT>, <TT>ArcPerpectives</TT>
            present <TT>NetArcs</TT>
            
            <LI><TT>FigList</TT> is a <TT>DiagramElement</TT> that
            contains others
         </UL>
         
         <H3>Collaborators</H3>
         
         <UL>
            <LI><TT>Layer</TT>
            
            <LI><TT>NetNode</TT>
            
            <LI><TT>NetArc</TT>
         </UL>
      </TD></TR>
   <TR></TR>
</TABLE></P>

<P><A NAME="NetPrimitive"></A>
<HR>
<TABLE BORDER=1>
   <TR>
      <TD WIDTH=314>
         <H2>NetPrimitive</H2>
      </TD><TD ROWSPAN=3>
         <P><IMG SRC="screenshots/net2.gif" WIDTH=256 HEIGHT=178
         X-SAS-UseImageWidth X-SAS-UseImageHeight ALIGN=bottom></P>
         
         <P>Shown here are three <TT>Perpective</TT>s and two
         <TT>ArcPerepectives</TT>. Not visible are the three
         <TT>NetNode</TT>s, twelve <TT>NetPort</TT>s, and two
         <TT>NetArc</TT> that represent the graph.
      </TD></TR>
   <TR>
      <TD ROWSPAN=2 WIDTH=314>
         <H3>Responsibilities</H3>
         
         <UL>
            <LI><TT>NetPrimitive</TT> is an abstract superclass for
            <TT>NetNode</TT>, <TT>NetPort</TT>, and <TT>NetArc</TT>
            
            <LI>Any <TT>NetPrimitive</TT> can have an underlying
            application object
            
            <LI><TT>NetNode</TT> represents a graph node
            
            <LI><TT>NetPort</TT> is a connection point on a node
            
            <LI><TT>NetArc</TT> is an arc between ports
            
            <LI><TT>NetNodes</TT> can handle events
            
            <LI><TT>NetPort</TT> and <TT>NetNode</TT> check for valid
            connections
         </UL>
         
         <H3>Collaborators</H3>
         
         <UL>
            <LI><TT>Perspective</TT>
            
            <LI><TT>ArcPerspective</TT>
            
            <LI>Arbitrary application objects
         </UL>
      </TD></TR>
   <TR></TR>
</TABLE></P>

<P><A NAME="Action"></A>
<HR>
<TABLE BORDER=1>
   <TR>
      <TD WIDTH=164>
         <H2>Action</H2>
      </TD><TD ROWSPAN=3>
         <P><IMG SRC="screenshots/auxwindows2.gif" WIDTH=453
         HEIGHT=334 X-SAS-UseImageWidth X-SAS-UseImageHeight
         ALIGN=bottom></P>
         
         <P>Buttons on the <TT>Palette</TT> contain <TT>Action</TT>s
         that are executed in the <TT>Editor</TT> when the button is
         pressed. <TT>Action</TT>s can also be contained in menu
         items or selected from a list. The "About" button gives
         user-level docuementation on the selected <TT>Action</TT>.
      </TD></TR>
   <TR>
      <TD ROWSPAN=2 WIDTH=164>
         <H3>Responsibilities</H3>
         
         <UL>
            <LI>Modify the document or environment in some way, e.g.,
            delete a <TT>DiagramElement</TT>, save document, or
            change the <TT>Mode</TT> of the <TT>Editor</TT>
            
            <LI>Record enough information to undo itself , and
            provide ability to undo itself (future)
            
            <LI>Provide a descriptive name and URL to user-level
            docuementation
         </UL>
         
         <H3>Collaborators</H3>
         
         <UL>
            <LI><TT>Editor</TT>
         </UL>
      </TD></TR>
   <TR></TR>
</TABLE></P>

<P><A NAME="Selection"></A>
<HR>
<TABLE BORDER=1>
   <TR>
      <TD WIDTH=314>
         <H2>Selection</H2>
      </TD><TD ROWSPAN=3>
         <P><IMG SRC="screenshots/selections.gif" WIDTH=256
         HEIGHT=178 X-SAS-UseImageWidth X-SAS-UseImageHeight
         ALIGN=bottom></P>
         
         <P>Three <TT>Selection</TT> objects: two
         <TT>SelectionHandle</TT>s that are visible, and one
         <TT>SelectionMultiple</TT> that contains them.
      </TD></TR>
   <TR>
      <TD ROWSPAN=2 WIDTH=314>
         <P>Responsibilities</P>
         
         <UL>
            <LI>Draw indications of which <TT>DiagramElement</TT>s
            are selected, e.g., handles
            
            <LI>Pass messages to the selected
            <TT>DiagramElement</TT>s
            
            <LI><TT>SelectionMultiple</TT> contains other
            <TT>Selections</TT>
         </UL>
         
         <P>Collaborators</P>
         
         <UL>
            <LI><TT>DiagramElement</TT>
         </UL>
      </TD></TR>
   <TR></TR>
</TABLE><A NAME="RedrawManager"></A></P>

<P>
<HR>
<TABLE BORDER=1>
   <TR>
      <TD WIDTH=314>
         <H2>RedrawManager</H2>
      </TD><TD ROWSPAN=3>
         <P><IMG SRC="screenshots/modify2.gif" WIDTH=256 HEIGHT=178
         X-SAS-UseImageWidth X-SAS-UseImageHeight ALIGN=bottom></P>
         
         <P>As the user resizes a <TT>FigRect</TT>, some exisiting
         green <TT>FigLines</TT> may need to be redrawn.
      </TD></TR>
   <TR>
      <TD ROWSPAN=2 WIDTH=314>
         <H3>Responsibilities</H3>
         
         <UL>
            <LI>Efficently redraw damaged sections of the window
            
            <LI>Store rectangles indicating damaged area
            
            <LI>Periodically force redraws of damaged areas, Try to
            maintain a specified frame-rate, independantly of machine
            speed
            
            <LI>Avoid screen-dirt and mutual exclusion by redrawing
            sychronously if possible
         </UL>
         
         <H3>Collaborators</H3>
         
         <UL>
            <LI><TT>Editor</TT>
         </UL>
      </TD></TR>
   <TR></TR>
</TABLE><A NAME="Adding a node"></A></P>

<P>
<HR>
(During this part of the presentation, each audiance member holds one
CRC card and pretends to be all instances of that class and its
subclasses. A ball is tossed from person to person to represent the
flow of control  in the system. Each person looks at their
responsibilities and says what they think they should do whenever
they have the ball. This activity was awkward, mainly because
audiance members did not understand the framework enough after only
40 minutes of presentation and discussion.)</P>

<H2>Use case: Adding a node to the diagram</H2>

<OL>
   <LI>User clicks on the node button on the palette
   
   <LI>User moves mouse into an <TT>Editor</TT>, the node is drawn
   whereever the mouse moves
   
   <LI>User clicks to specify the position of the node
   
   <LI>Node is added to the diagram, Node is selected
</OL>

<H2><A NAME="Selecting multiple"></A>
<HR>
Use case: Selecting multiple objects</H2>

<OL>
   <LI>User presses and holds the mouse button at one point
   
   <LI>User drags mouse to another point, a selection rectangle is
   shown
   
   <LI>User releases mouse button, <TT>DiagramElement</TT>s in the
   rectangle are selected
</OL>

<H2><A NAME="Drawing a polygon"></A>
<HR>
Use case: Drawing a polygon</H2>

<OL>
   <LI>User clicks on Polygon button in the palette
   
   <LI>User moves mouse into an <TT>Editor</TT>
   
   <LI>User clicks once to start the polygon
   
   <LI>Moving the mouse moves the next point, clicking places that
   point
   
   <LI>Double click finishes the polygon
</OL>

<H2><A NAME="Adding a label"></A>
<HR>
Use case: Adding a label</H2>

<OL>
   <LI>User clicks on Text button in the palette
   
   <LI>User moves mouse into an <TT>Editor</TT>
   
   <LI>User drags out the rectangle that the text will be placed in
   
   <LI>The (empty) text object is added to the diagram and selected
   
   <LI>Typing will add characters to the selected text
</OL>

<H2><A NAME="Booch"></A>
<HR>
Use case: Implementing an Booch class browser</H2>

<OL>
   <LI>Subclass <TT>Fig</TT> to make <TT>FigCloud</TT>
   
   <LI>Subclass <TT>NetNode</TT> to make class <TT>BoochNode</TT>,
   define attributes, model is <TT>BoochClass</TT>
   
   <LI>Subclass <TT>NetArc</TT> to make class
   <TT>BoochSubclassArc</TT>
   
   <LI>Subclass <TT>Perspective</TT> to make class
   <TT>BoochClassPerpective</TT>, implement draw method
   
   <LI>Subclass <TT>ArcPerepective</TT> to make class
   <TT>BoochSubclassPerspective</TT>
   
   <LI>Build GUI windows to edit attributes on these nodes and arcs
   
   <LI>Define <TT>ActionToggleAbstract</TT>
</OL>

<H2><A NAME="Open design problems"></A>
<HR>
Open design problems and issues</H2>

<UL>
   <LI>There are already over 100 classes, too many classes make it
   seem hard to understand
   
   <LI>Support for undo, multiple perspectives, zooming, etc.
   
   <LI>What is the best way to document, explain this framework
   
   <LI>Not enough demos
</UL>

<H2><A NAME="previous work"></A>
<HR>
Some previous work on graph editing</H2>

<UL>
   <LI>UniDraw. Done at Stanford with Interviews C++ class framework
   
   <LI>HotDraw. Done by various people, including John Brant at UIUC
   in Smalltalk
   
   <LI>jkit/GO. Java version of HotDraw done by ObjectSpace, inc
   
   <LI>BPE. Done by people at Rockwell International, Smalltalk, C++,
   Objective/C, Java
   
   <LI>DOT. Graph visualization project at AT&amp;T.
   
   <LI>VCG. Visualization of Compiler Graphs.
   
   <LI>Tom Sawyer Graph Toolkit. Tom Sawyer Software.
</UL>
</BODY>
</HTML>
